

快速排序比冒泡排序要快的一种排序方法。其也是从冒泡排序演变而来的。

之所以比冒泡排序快是因为使用了分治法。  

同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置 来达到排序的目的。
不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端，而快速排序则
在每一轮挑选一个基准元素，

并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分。 这种思路就叫作分治法。  



假如给出一个8个元素的数列，一般情况下，使用冒泡排序需要比较7轮，每一 轮把1个元素移动到数列的一端，时间复杂度是O(n2)。
在分治法的思想下，原数列在每一轮都被拆分成两部分，每一部分
在下一轮又分别被拆分成两部分，直到不可再分为止。
每一轮的比较和交换，需要把数组全部元素都遍历一遍，时间复杂度是O(n)。 这样的遍历一共需要多少轮呢?假如元素个数是n，那么平均情况下需要logn轮，因 此快速排序算法总体的平均时间复杂度是O(nlogn)。

### 基准元素的选择 

最简单的方式是选择数列的第1个元素。  

这种选择在绝大多数情况下是没有问题的。但是，假如有一个原本逆序的数
列，期望排序成顺序数列，那么会出现什么情况呢? 


哎呀，整个数列并没有被分成两半，每一轮都只确定了基准元素的位置。 
是呀，在这种情况下，数列的第1个元素要么是最小值，要么是最大值，根本无法发挥分治法的优势。  

在这种极端情况下，快速排序需要进行n轮，时间复杂度退化成了O(n2)。  

那么，该怎么避免这种情况发生呢?
其实很简单，我们可以随机选择一个元素作为基准元素，并且让基准元素和数 列首元素交换位置
